package sort;

import java.util.Arrays;

public class RadixSort {

    public static void main(String[] args) {
        int[] array = {329, 457, 657, 839, 436, 720, 355};
        radixSort(array);
//        countingSort(array, 1);
    }

    public static void radixSort(int[] array) {
        int[] sortArray = array;
        for (int i = 1; i <= 3; i++) {
            sortArray = countingSort(sortArray, i);
        }
//        System.out.println(Arrays.toString(sortArray));
    }

    public static int[] countingSort(int[] array, int radixIndex) {
        int[] tempArray = new int[10];//纪录相同数的个数
        int[] tempIndexArray = new int[10];//存储数组排序的真实位置

        for (int a : array) {
            tempArray[getRadix(a, radixIndex)] += 1;
        }

//        将原来的计数排序稍作变换，增加一个数组，两个数组。分别纪录真实的排序下标和相同数的个数
        tempIndexArray[0] = tempArray[0];
        for (int i = 1; i < tempArray.length; i++) {
            tempIndexArray[i] = tempArray[i] + tempIndexArray[i - 1];
//            tempArray[i] += tempArray[i - 1];
        }

/*        System.out.println(Arrays.toString(tempIndexArray));
        System.out.println(Arrays.toString(tempArray));*/

        int[] sortedArray = new int[array.length];
        for (int value : array) {
            int tempIndex = getRadix(value, radixIndex);
        /** 位置下标值减去相同数个数就是排序的下标
         * 这里对原来的计数排序做了个变换。
         * 原来的计数排序，只是根据temps数组来确定下标位置，然后减一，
         * 当有相同的数，则会放到上一个已排序相同数的前面，这样就调换了在上一次排序中的相同数的位置。
         * 在这里我们稍加改造。
         */
            sortedArray[tempIndexArray[tempIndex] - tempArray[tempIndex]] = value;
            tempArray[tempIndex]--;
        }
        System.out.println(Arrays.toString(sortedArray));
        return sortedArray;
    }

    private static int getRadix(int number, int radixIndex) {
        if (radixIndex == 1) return number % 10;
        else return number / (int) Math.pow(10, (radixIndex - 1)) % 10;
    }
}
